package com.lql.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 希尔排序
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 1, 7, 0, 23, 45, 34, 2, 4, 5, 3};
        int[] array1 = {1, 2, 3, 1, 7, 0, 23, 45, 34, 2, 4, 5, 3};
        int[] ints = new int[8000000];
        Random random = new Random();
        for (int i = 0; i < 8000000; i++) {
            ints[i] = random.nextInt(8000000);
        }
//        shellSorted(array);
        shellSorted2(ints);
    }

    /**
     * 交换法实现希尔排序
     *
     * @param arrays 待排序的数组
     */
    public static void shellSorted(int[] arrays) {
        long startTime = System.currentTimeMillis();
        System.out.println("开始：" + startTime);
        int temp;
        for (int gap = arrays.length / 2; gap > 0; gap /= 2) {
            //gap表示分组数，假设是10个数据则分为10/5=2组、5/2=2组和2/2=1组
//            System.out.println(gap);
            for (int i = gap; i < arrays.length; i++) {
                //分组
                for (int j = i - gap; j >= 0; j -= gap) {
                    //对组内元素进行排序,交换
                    if (arrays[j] > arrays[j + gap]) {
                        //当组内的前一个元素大于后一个元素时进行交换
                        temp = arrays[j];
                        arrays[j] = arrays[j + gap];
                        arrays[j + gap] = temp;
                    }
                }
            }
//            System.out.println(Arrays.toString(arrays));
        }
        long endTime = System.currentTimeMillis();
        System.out.println("结束：" + endTime);
        float l = (endTime - startTime) / 1000f;
        System.out.println("总时间：" + l + "秒");
    }

    /**
     * 移位法（插入法）实现希尔排序
     *
     * @param arrays 待排序的数组
     */
    public static void shellSorted2(int[] arrays) {
        long startTime = System.currentTimeMillis();
        System.out.println("开始：" + startTime);
        int insertValue;
        int p;
        for (int gap = arrays.length / 2; gap > 0; gap /= 2) {
            //gap表示分组数，假设是10个数据则分为10/2=5组、5/2=2组和2/2=1组
//            System.out.println(gap);
            for (int i = gap; i < arrays.length; i++) {
                p = i;
                insertValue = arrays[i];
                //分组
                while (p - gap >= 0 && insertValue < arrays[p - gap]) {
                    arrays[p] = arrays[p - gap];
                    p -= gap;
                }
                arrays[p] = insertValue;
            }
        }

        long endTime = System.currentTimeMillis();
        System.out.println("结束：" + endTime);
        float l = (endTime - startTime) / 1000f;
        System.out.println("总时间：" + l + "秒");
    }
}